from typing import List
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        s_len ,p_len = len(s),len(p)
        if s_len < p_len:
            return []
        ans = []
        s_count = [0]*26
        p_count = [0]*26
        for i in range(p_len):
            s_count[ord(s[i])-97]+=1
            p_count[ord(p[i])-97]+=1
        print(s_count,p_count)
        if s_count == p_count:
            ans.append(0)
        for i in range(s_len-p_len):
            s_count[ord(s[i])-97]-=1
            print("i=",s_count)
            s_count[ord(s[i+p_len])-97]+=1
            print("i+p_len=",s_count)
            if s_count==p_count:
                ans.append(i+1)
        return ans
    '''
    复杂度分析
    时间复杂度：O(m+(n−m)×Σ)，其中 n 为字符串 s 的长度，m 为字符串 p 的长度，Σ 为所有可能的字符数。
    我们需要 O(m) 来统计字符串 p 中每种字母的数量；需要 O(m) 来初始化滑动窗口；
    需要判断 n−m+1 个滑动窗口中每种字母的数量是否与字符串 p 中每种字母的数量相同，每次判断需要 O(Σ) 。因为 s 和 p 仅包含小写字母，所以 Σ=26。
    空间复杂度：O(Σ)。用于存储字符串 p 和滑动窗口中每种字母的数量。
    '''
    def findAnagrams2(self, s: str, p: str) -> List[int]:
        s_len,p_len=len(s),len(p)
        if s_len < p_len:
            return []
        ans = []
        count = [0]*26
        for i in range(p_len):
            count[ord(s[i])-97]+=1
            count[ord(p[i])-97]-=1
        differ = [c!=0 for c in count].count(True)
        print(f"differ={differ}",differ,count)
        if differ == 0:
            ans.append(0)
        for i in range(s_len-p_len):
            if count[ord(s[i])-97] == 1:
                differ-=1
            elif count[ord(s[i])-97] ==0:
                differ+=1
            print(f"====={i}=======")
            print(f"i={differ}",differ, count[ord(s[i])-97],count)
            count[ord(s[i])-97] -=1
            print(f"i={i}",count)
            if count[ord(s[i+p_len])-97]==-1:
                differ-=1
            elif count[ord(s[i+p_len])-97]==0:
                differ +=1
            print(f"i+p_len={differ}",differ)
            count[ord(s[i+p_len])-97]+=1
            print(f"i+p_len={i+p_len}",count)

            if differ==0:
                ans.append(i+1)
        return ans


# print(Solution().findAnagrams(s = "cbaebabacd", p = "abc"))
print(Solution().findAnagrams2(s = "cbaebabacd", p = "abc"))
